/**
*
* @author Anastasiya
*
*/

#include "ozawa.h"
#include "ozawamsg.h"
#include "util.h"
#include "printing.h"
#include <ogdf/basic/basic.h>
#include <ogdf/basic/Graph_d.h>
#include <ogdf/basic/List.h>
#include <ogdf/planarity/FastPlanarSubgraph.h>
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/basic/extended_graph_alg.h>
#include <time.h>
#include <string>

using namespace std;
using namespace ogdf;
using namespace ozw;
using namespace utl;


const string OzawaAlgorithm::ALGORITHM_NAME = "ozawa";

OzawaException::OzawaException(const std::string message){
	this->message = message;
}

OzawaAlgorithm::OzawaAlgorithm(const Graph& graph, const Printer* printer){
	this->graph = new Graph(graph);
	this->printer = printer;
}

string OzawaAlgorithm::getName(){
	return ALGORITHM_NAME;
}

OzawaAlgorithm::~OzawaAlgorithm(){
	if (tree.root() != NULL){

		tree.Cleanup();
	}
	cleanMap(&allPQTreeLeaves);
	cleanMap(&reducingPQTreeLeaves);

	delete graph;
}
void OzawaAlgorithm::execute(const string inputFileName, const OzawaResultHandler* resultHandler, const Printer* printer){
	Graph graph;
	graph.readGML(inputFileName.c_str());

	OzawaAlgorithm algorithm(graph, printer);

	try{
		algorithm.execute();
		resultHandler->resultProcessionFunction(inputFileName, algorithm.getGraph(), 
			algorithm.getDeletedEdgesCount(), algorithm.getExecutionTime());
	}catch(OzawaException &ex){
		resultHandler->errorProcessionFunction(inputFileName, ex.message);
	}catch(int){
		resultHandler->errorProcessionFunction(inputFileName, PROCESS_ERROR_UNKNOWN_ERROR);
	}
}

void OzawaAlgorithm::execute(){

	// Test if graph can be planarized by this algorithm
	assertAlgorithmApplicable();

	GetSystemTime(&startTime);

	// Compute st-numbering for graph
	STNumbering stNumbering(*graph, 0);
	computeStNumbering(&stNumbering);

	Array<node> stNumberedNodes(graph->numberOfNodes());

	// Computing PQ-leaves for each node. This leaves will be used for PQ-trees building
	printer->logEvent(PROCESS_MESSAGE_COMPUTING_LEAFS);
	computePQTreeLeaves(&stNumbering, &allPQTreeLeaves, &stNumberedNodes);

	// Computing PQ-leaves which will be used for PQ-tree reducing.
	printer->logEvent(PROCESS_MESSAGE_COMPUTING_REDUCE_LEAFS);
	computeLeavesForReduce(&allPQTreeLeaves, &reducingPQTreeLeaves);

	//Reduce PQ-tree
	buildAndReduceTree(&allPQTreeLeaves, &reducingPQTreeLeaves, &stNumberedNodes);

	// Deletes accumulated edges from graph
	printer->logEvent(PROCESS_MESSAGE_DELETING_EDGES);
	deleteComputedEdgesFromGraph();

	GetSystemTime(&endTime);

	printer->logEvent(PROCESS_MESSAGE_WRITING_RESULT);
	printer->testEnded();
}

/**
*
* Computes st-numbering for graph g. Returns pointer to STNumbering contains numbering
*
*/
void OzawaAlgorithm::computeStNumbering(STNumbering* stNumbering){
	// Compute st-numbering
	printer->logEvent(PROCESS_MESSAGE_MAKING_ST_NUMBERING);
	int n = stNumber(*graph, *stNumbering);
	if(n == 0){
		OzawaException ex(PROCESS_ERROR_ST_NUMBERING); 
		throw ex;
	}
	OGDF_ASSERT_IF(dlConsistencyChecks, testSTnumber(*graph, *stNumbering, n));
}


/**
*
* Computes leaves wivh will be used for reducing PQ-tree. Computes leaves for each graph node.
*
*/
void OzawaAlgorithm::computeLeavesForReduce(NodesToPQLeavesMap* treeLeavesMap, NodesToPQLeavesMap* reduceLeavesMap){
	node n;
	forall_nodes(n, *graph){
		SListIterator<PlanarPQTreeLeaf*> it;
		for (it = (*treeLeavesMap)[n]->begin(); it.valid(); ++it)
		{
			PlanarPQTreeLeaf* leaf = *it;
			EdgeElement* edgeInfo = leaf->userStructKey();
			node oppositeNode = edgeInfo->opposite(n);

			if(reduceLeavesMap->count(oppositeNode) == 0){
				PQTreeLeavesList* lst = new PQTreeLeavesList();
				pair<node, PQTreeLeavesList*> p(oppositeNode, lst);
				reduceLeavesMap->insert(p);
			}
			(*reduceLeavesMap)[oppositeNode]->pushFront(leaf);
		}
	}
}

/**
*
* Computes PQ-tree leaves for each node. These leaves will be used for PQ-tree building 
*
*/
void OzawaAlgorithm::computePQTreeLeaves(const STNumbering* stNumbering, NodesToPQLeavesMap* leafsMap, Array<node>* stNumberedNodes){
	node n;
	forall_nodes(n, *graph){
		pair<node, PQTreeLeavesList*> p(n, computePQTreeLeaves(&n, stNumbering));
		leafsMap->insert(p);
		int nodeStNumber = (*stNumbering)[n];
		(*stNumberedNodes)[nodeStNumber - 1] = n;
	}
}

/**
*
* Computes PQ-tree leaves for node.
*
*/
PQTreeLeavesList* OzawaAlgorithm::computePQTreeLeaves(const node* n, const STNumbering* stNumbering){
	PQTreeLeavesList* leafsForNode = new PQTreeLeavesList();
	edge e;
	forall_adj_edges(e, *n){
		if ((*stNumbering)[e->opposite(*n)] > (*stNumbering)[*n])
		{
			PlanarPQTreeLeaf* L = new PlanarPQTreeLeaf(e);
			leafsForNode->pushFront(L);
		}
	}
	return leafsForNode;
}


void OzawaAlgorithm::assertAlgorithmApplicable() const{
	if(graph->numberOfNodes() < 3){
		// Check if graph have at least 3 nodes
		OzawaException ex(PROCESS_ERROR_MUST_CONTAINT_MORE_THEN_3_NODES);
		throw ex;
	}
	if(!isBiconnected(*graph) || !isSimple(*graph)){
		// Test if graph simple and biconnected. If not, st-numbering process will fail
		OzawaException ex(PROCESS_ERROR_MUST_BE_SIMPLE);
		throw ex;
	}
}

/**
* Builds and reduces PQ-tree
*
*/
void OzawaAlgorithm::buildAndReduceTree(NodesToPQLeavesMap* allPQTreeLeaves, NodesToPQLeavesMap* reducingPQTreeLeaves, const Array<node>* stNumberedNodes){
	int ind;

	printer->logEvent(PROCESS_MESSAGE_COMPUTING_PQ_TREES);
	// Start tree building-reducing process
	forall_arrayindices(ind, *stNumberedNodes){
		// (1.1 if ind = 0, 2.1 overwise)
		node nextNode = (*stNumberedNodes)[ind];
		PQTreeLeavesList* leaves = (*allPQTreeLeaves)[nextNode];
		PQTreeLeavesList* reduceLeaves = (*reducingPQTreeLeaves)[nextNode];
		logReducingStep(ind);
		if(ind == 0){
			// Build first tree (T1) (1.2)
			tree.Initialize(*leaves);
		}else{
			// (2.2 - 5)
			makeNextReduceStep(leaves, reduceLeaves);
		}
	}
}

void OzawaAlgorithm::logReducingStep(int stepNumber) const{
	if(stepNumber == 0){
		printer->logEvent(PROCESS_MESSAGE_INITIALIZING_FIRST_TREE);
	}else{
		printer->logEvent(PROCESS_MESSAGE_REDUCING_TREE + numberToString(stepNumber));
	}
}

void OzawaAlgorithm::makeNextReduceStep(PQTreeLeavesList* leaves, PQTreeLeavesList* reduceLeaves){
	SList<PQLeafKey<edge, whaInfo*, bool>*> eliminatedKeys;

	// Tests if we can reduce tree (Tn) (5)
	if(tree.Reduction(*reduceLeaves, eliminatedKeys)){
		// Accumulates edges to be deleted from graph
		edgesToDelete.conc(eliminatedKeys);
		// Replaces pertient root with leaves corresponded to node n (2.2)
		tree.ReplaceRoot(*leaves);
		// Remove pertient nodes (4)
		tree.emptyAllPertinentNodes();
	}else{
		OzawaException ex(PROCESS_ERROR_REDUCING_FAILED);
		throw ex;
	}
}


/**
*
* Deletes edges (edgesToDelete) from graph (g)
*
*/
void OzawaAlgorithm::deleteComputedEdgesFromGraph() const{
	SListConstIterator<PQLeafKey<edge, whaInfo*, bool>*> edges = edgesToDelete.begin();
	while(edges != edgesToDelete.end()){
		graph->delEdge((*edges)->userStructKey());
		edges++;
	}
}


ULONGLONG OzawaAlgorithm::getExecutionTime() const{
	return calculateTimeDifference(startTime, endTime);
}
const Graph* OzawaAlgorithm::getGraph() const{
	return graph;
}
int OzawaAlgorithm::getDeletedEdgesCount() const{
	return edgesToDelete.size();
}

void OzawaAlgorithm::cleanMap(NodesToPQLeavesMap* map){
	NodesToPQLeavesMap::iterator leavesIterator = map->begin();
	while(leavesIterator != map->end()){
		delete leavesIterator->second;
		leavesIterator++;
	}
}
